package com.yuan.algorithms.practice201511;

/**
 * @author YouYuan
 * <br>E-mail:1265161633@qq.com
 * <br>创建时间：2015年11月7日 上午9:22:17
 * <br>说明:一个4*4的矩阵，在其中填充0~9的数字，使得每行每列以及两条对角线上组成的4位数均为可逆素数。
 *         可逆素数定义：如果一个数n是素数，并且它的逆序数也是素数，则称其为可逆素数。
 */
public class 可逆素数矩阵 {

	static int[] arr = new int[204];
	static int[][] map = new int[4][4];
	public static void main(String[] args) {
		long start, end;
		start = System.currentTimeMillis();
		System.out.println("Start:"+start);
		for (int i = 1001, index = 0; i < 9999; i+=2) {
			if (isReversiblePrime(i)) {
				arr[index++] = i;
			}
		}
//		System.out.println(judge(1193) +" "+judge(13) +" "+judge(37) +" "+judge(9931) +" "+judge(1031) +" "+judge(9013) +" ");
		System.out.println(isReversiblePrime(9173));
		System.out.println(isReversiblePrime(9467));
		System.out.println(isReversiblePrime(3803));
		System.out.println(isReversiblePrime(1733));
		System.out.println(isReversiblePrime(9403));
		System.out.println(isReversiblePrime(1863));
//		f(0);
		end = System.currentTimeMillis();
		System.out.println("End:"+end);
		System.out.println("总用时："+(end-start));
	}
	
	/**
	 * 判断是否是可逆序素数
	 * @param i
	 * @return
	 */
	private static boolean isReversiblePrime(int i) {
		return judge(i) & judge(reverse(i));
	}

	/**
	 * 用可逆序素数进行排列组合，寻找可能的解
	 * @param current
	 */
	private static void f(int current) {
		if (current == 4) {
			if (isAnswer()) {
				for (int i = 0; i < 4; i++) {
					for (int j = 0; j < 4; j++) {
						System.out.print(map[i][j]);
					}
				}
				System.out.println();
			}
			return;
		}
		for (int j = 0, len = arr.length; j < len; j++) {
			fill(arr[j], current);
			f(current+1);
		}
	}

	/**
	 * 判断是否是可逆序素数矩阵
	 * @return
	 */
	private static boolean isAnswer() {
		//去除以0开头的数字
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if ((i == 0 || i == 3 || j == 0 || j == 3) && map[i][j] == 0) {
					return false;
				}
			}
		}
		//判断列
		for (int i = 0; i < 4; i++) {
			String t = "";
			for (int j = 0; j < 4; j++) {
				t += map[j][i];
			}
			if (!isReversiblePrime(Integer.parseInt(t))) {
				return false;
			}
		}
		
		//判断对角线
		String t = "";
		for (int i = 0; i < 4; i++) {
			t += map[i][i];
		}
		if (!isReversiblePrime(Integer.parseInt(t))) {
			return false;
		}
		t = "";
		for (int i = 0, j = 3; j >= 0; j--, i++) {
			t += map[i][i];
		}
		if (!isReversiblePrime(Integer.parseInt(t))) {
			return false;
		}
		return true;
		
	}

	/**
	 * 填充矩阵
	 * @param data
	 * @param current
	 */
	private static void fill(int data, int current) {
		String t = ""+data;
		for (int i = 0; i < 4; i++) {
			map[current][i] = Integer.parseInt(""+t.charAt(i)) ;
		}
	}

	/**
	 * 求逆序数
	 * @param i
	 * @return
	 */
	private static int reverse(int i) {
		String t = "" + i;
		StringBuffer sbf = new StringBuffer();
		sbf.append(t);
		t = sbf.reverse().toString();
		return Integer.parseInt(t);
		
	}

	/**
	 * 判断素数
	 * @param i
	 * @return
	 */
	private static boolean judge(int i) {
		if ((i & 1) == 0) {
			return false;
		}
		for (int j = 3; j <= Math.sqrt(i); j+=2) {
			if (i % j == 0) {
				return false;
			}
		}
		return true;
	}

}
